package cn.njupt;

import java.util.*;

public class ListGraph<V, E> extends Graph<V, E> {

    private Map<V, Vertex<V, E>> verticesMap = new HashMap<>();
    private Set<Edge<V, E>> edges = new HashSet<>();


    public ListGraph(WeightManager<E> weightManager){
        super(weightManager);
    }

    public ListGraph(){

    }

    private Comparator<Edge<V,E>> edgeComparator=(Edge<V,E> edge1,Edge<V,E> edge2)->{
       return weightManager.compare(edge1.weight,edge2.weight);
    };



    public void print() {
        System.out.println("顶点------------------------");
        verticesMap.forEach((V v, Vertex<V, E> vertex) -> {
            System.out.println(v);
            System.out.println("in------");
            System.out.println(vertex.inEdges);
            System.out.println("out------");
            System.out.println(vertex.outEdges);
        });
        System.out.println("边------------------------");
        edges.forEach(edge -> {
            System.out.println(edge);
        });
    }

    @Override
    public int edgesSize() {
        return edges.size();
    }

    @Override
    public int verticesSize() {
        return verticesMap.size();
    }

    @Override
    public void addVertex(V value) {
        if (!verticesMap.containsKey(value)) {
            Vertex<V, E> vertex = new Vertex<>(value);
            verticesMap.put(value, vertex);
        }
    }

    @Override
    public void addEdge(V from, V to, E weight) {
        //如果本来就存在这条边,就替换权值;不存在就创建
        Vertex<V, E> fromVertex = verticesMap.get(from);
        if (fromVertex == null) {
            fromVertex = new Vertex<>(from);
            verticesMap.put(from, fromVertex);
        }
        Vertex<V, E> toVertex = verticesMap.get(to);
        if (toVertex == null) {
            toVertex = new Vertex<>(to);
            verticesMap.put(to, toVertex);
        }
        Edge<V, E> edge = new Edge<>(fromVertex, toVertex);
        edge.weight = weight;

//      如果存在这条边，就需要删除重新添加，remove()操作是根据edge边的hashcode删除的，所以删除重新添加是比较省事的
//      拿出来覆盖权重太麻烦了，需要从fromVertex和toVertex以及edges中拿出然后再覆盖
        if (fromVertex.outEdges.remove(edge)) {
            toVertex.inEdges.remove(edge);
            edges.remove(edge);
        }
        fromVertex.outEdges.add(edge);
        toVertex.inEdges.add(edge);
        edges.add(edge);
    }


    @Override
    public void addEdge(V from, V to) {
        addEdge(from, to, null);
    }


    @Override
    public void removeEdge(V from, V to) {
        //删除边
        Vertex<V, E> fromVertex = verticesMap.get(from);
        Vertex<V, E> toVertex = verticesMap.get(to);
        if (fromVertex == null || toVertex == null) return;
        Edge<V, E> edge = new Edge<>(fromVertex, toVertex);
        if (edges.remove(edge)) {
            //存在这条边
            fromVertex.outEdges.remove(edge);
            toVertex.inEdges.remove(edge);
        }
    }

    /**
     * 删除顶点,如果需要一边遍历一边删除，最好使用迭代器
     *
     * @param value
     */
    @Override
    public void removeVertex(V value) {
        Vertex<V, E> vertex = verticesMap.remove(value);
        if (vertex == null) return;
        for (Iterator<Edge<V, E>> it = vertex.outEdges.iterator(); it.hasNext(); ) {
            Edge<V, E> edge = it.next();
            edge.to.inEdges.remove(edge);
            // 将当前遍历到的元素edge从集合vertex.outEdges中删掉
            it.remove();
            edges.remove(edge);
        }
        for (Iterator<Edge<V, E>> it = vertex.inEdges.iterator(); it.hasNext(); ) {
            Edge<V, E> edge = it.next();
            edge.from.outEdges.remove(edge);
            it.remove();
            edges.remove(edge);
        }
    }

    //广度优先遍历
    @Override
    public void bfs(V v,Visitor<V> visitor) {
        Vertex<V, E> vertex = verticesMap.get(v);
        if (vertex == null) return;
        Queue<Vertex<V, E>> queue = new LinkedList<>();
        queue.offer(vertex);
        HashSet<Vertex<V, E>> register = new HashSet<>();
        register.add(vertex);
        while (!queue.isEmpty()) {
            vertex = queue.poll();
            if(visitor.visit(vertex.value))break;
//            System.out.println(vertex.value);
            vertex.outEdges.forEach((Edge<V, E> edge) -> {
                if (!register.contains(edge.to)) {
                    register.add(edge.to);
                    queue.offer(edge.to);
                }
            });
        }
    }

//  深度优先非递归方式
    @Override
    public void dfs(V v) {
        Vertex<V,E> vertex=verticesMap.get(v);
        if(vertex==null)return;
        HashSet<Vertex<V,E>> visitedVertices=new HashSet<>();
        Stack<Vertex> stack=new Stack<>();
        stack.push(vertex);
        visitedVertices.add(vertex);
        while(!stack.isEmpty()){
            vertex=stack.pop();
            for(Edge<V,E> edge:vertex.outEdges){
                if(visitedVertices.contains(edge.to)){
                    continue;
                }
                stack.push(edge.to);
                visitedVertices.add(edge.to);
            }
            System.out.println(vertex.value);
        }

    }

    @Override
    public List<V> topologicalSort() {
        List<V> result=new ArrayList<>();

        Queue<Vertex<V,E>> queue=new LinkedList<>();

        Map<Vertex<V,E>,Integer> map=new HashMap<>();
        verticesMap.forEach((V v,Vertex<V,E> vertex)->{
            if(vertex.inEdges.size()==0){
                queue.offer(vertex);
            }else {
                map.put(vertex,vertex.inEdges.size());
            }
        });

        while(!queue.isEmpty()){
            Vertex<V,E> vertex=queue.poll();
            result.add(vertex.value);

            for (Edge<V,E> edge:vertex.outEdges){
                int indegree=map.get(edge.to)-1;

                if(indegree==0){
                    queue.offer(edge.to);
                }else{
                    map.put(edge.to,indegree);
                }
            }

        }
        return result;

    }

    @Override
    public Set<EdgeInfo<V, E>> mst() {
        return kruskal();
    }

    @Override
    public Map<V, PathInfo<V, E>> shortestPath(V begin) {
        //起始顶点
        Vertex<V, E> beginVertex = verticesMap.get(begin);
        if(beginVertex==null)return null;
        Map<V,PathInfo<V,E>> pathes=new HashMap<>();

        HashSet<Vertex> visited=new HashSet<>();
        PriorityQueue<Edge<V,E>> queue=new PriorityQueue<>(edgeComparator);
        for (Edge<V, E> outEdge : beginVertex.outEdges) {
            queue.offer(outEdge);
            PathInfo<V,E> pathInfo=new PathInfo<>(outEdge.weight);
            pathInfo.getList().add(outEdge.edgeInfo());
            pathes.put(outEdge.to.value,pathInfo);
        }
        visited.add(beginVertex);
        int vertexSize=verticesMap.size()-1;
        while(!queue.isEmpty() && visited.size()<vertexSize){

            Edge<V, E> edges = queue.poll();
            visited.add(edges.to);
            Set<Edge<V, E>> outEdges = edges.to.outEdges;
            outEdges.forEach(edge->{
                Vertex<V,E> to =edge.to;
                if(!visited.contains(to)){
                    //拿到比如A->B->C即A->B的最短路径
                    PathInfo<V,E> prePathInfo = pathes.get(edge.from.value);
                    E sumWeight=weightManager.add(prePathInfo.getWeight(),edge.weight);

                        //之前到to顶点最小路径
                        PathInfo<V,E> curPathInfo = pathes.get(to.value);
                        if(!pathes.containsKey(to.value) ||weightManager.compare(curPathInfo.getWeight(), sumWeight)>0  ){
                            PathInfo<V,E> pathInfo=new PathInfo<>(sumWeight);

                            LinkedList<EdgeInfo<V, E>> list = pathInfo.getList();

                            LinkedList<EdgeInfo<V, E>> prePath = pathes.get(edge.from.value).getList();
                            list.addAll(prePath);
                            list.add(edge.edgeInfo());

                            pathes.put(to.value,pathInfo);

                        }

                    queue.offer(edge);
                }

            });
        }

        return pathes;
    }





//    @Override
//    public Map<V, E> shortestPath(V begin) {
//        //起始顶点
//        Vertex<V, E> beginVertex = verticesMap.get(begin);
//        if(beginVertex==null)return null;
//        Map<V,E> pathes=new HashMap<>();
//
//        HashSet<Vertex> visited=new HashSet<>();
//        PriorityQueue<Edge<V,E>> queue=new PriorityQueue<>(edgeComparator);
//        for (Edge<V, E> outEdge : beginVertex.outEdges) {
//            queue.offer(outEdge);
//            pathes.put(outEdge.to.value,outEdge.weight);
//        }
//        visited.add(beginVertex);
//        int vertexSize=verticesMap.size()-1;
//        while(!queue.isEmpty() && visited.size()<vertexSize){
//
//            Edge<V, E> edges = queue.poll();
//            visited.add(edges.to);
//            Set<Edge<V, E>> outEdges = edges.to.outEdges;
//            outEdges.forEach(edge->{
//                Vertex<V,E> to =edge.to;
//                if(!visited.contains(to)){
//                    //拿到比如A->B->C即A->B的最短路径
//                    E preWeight = pathes.get(edge.from.value);
//                    E sumWeight=weightManager.add(preWeight,edge.weight);
//
//                    if(pathes.containsKey(to.value)){
//                        //之前到to顶点最小路径
//                        E curWeight = pathes.get(to.value);
//                        if(weightManager.compare(curWeight,sumWeight)>0){
//                            pathes.put(to.value,sumWeight);
//                        }
////                        edge.weight=sumWeight;
//
//                    }else{
//                        pathes.put(to.value,edge.weight);
////                        edge.weight=sumWeight;
//
//                    }
//                    queue.offer(edge);
//                }
//
//            });
//        }
//
//        return pathes;
//    }

    /**
     * Prim算法  最小生成树
     * @return
     */

    public Set<EdgeInfo<V, E>> prim() {
        PriorityQueue<Edge<V,E>> queue=new PriorityQueue<>(edgeComparator);
        //遍历所有的顶点
        Collection<Vertex<V, E>> values = verticesMap.values();
        Iterator<Vertex<V, E>> it = values.iterator();
        if(!it.hasNext())return null;

        //随机取出一个顶点
        Vertex<V, E> vertex = it.next();

        //已经增加的顶点
        Set<Vertex<V,E>> visitedVertices=new HashSet<>();

        //添加取出顶点的所有边
        visitedVertices.add(vertex);
        for(Edge<V,E> edge:vertex.outEdges){
            queue.offer(edge);
        }

        //存放结果
        Set<EdgeInfo<V,E>> set=new HashSet<>();

        int vertices=values.size();
        while(visitedVertices.size()<vertices && !queue.isEmpty()){
            Edge<V, E> edge = queue.poll();
            EdgeInfo<V, E> info = edge.edgeInfo();
            Vertex<V, E> to = edge.to;
            if(visitedVertices.contains(to))continue;
            visitedVertices.add(to);
            set.add(info);
            for(Edge<V,E> e:edge.to.outEdges){
                queue.offer(e);
            }
        }
        return set;
    }

    public Set<EdgeInfo<V, E>> kruskal() {
        PriorityQueue<Edge<V,E>> queue=new PriorityQueue<>(edgeComparator);
        edges.forEach(edge->queue.add(edge));

        Set<EdgeInfo<V,E>> edgeInfos=new HashSet<>();
        UnionFind<Vertex<V,E>> unionFind=new UnionFind<>();
        verticesMap.forEach((V v,Vertex<V,E> vertex)->{
            unionFind.makeSets(vertex);
        });
        int edges=verticesMap.size()-1;
        //这边需要用边的数量进行比较，而不是顶点数量，边的数量应该是顶点数量减一
        while(!queue.isEmpty() && edgeInfos.size()<edges){
            Edge<V, E> edge = queue.poll();

            Vertex<V,E> to=edge.to;
            Vertex<V,E> from =edge.from;
            if(unionFind.isSame(to,from))continue;

            edgeInfos.add(edge.edgeInfo());
            //合并
            unionFind.union(to,from);
        }
        return edgeInfos;
    }














/*    public int cmp(E e1,E e2){
        if(e1 instanceof Comparable){
            return ((Comparable<E>)(e1)).compareTo(e2);
        }
        return comparator.compare(e1,e2);
    }*/
    //深度优先遍历递归方式
//    @Override
//    public void dfs(V v) {
//        Vertex<V, E> vertex = verticesMap.get(v);
//        if (vertex == null) return;
//        dfs(vertex,new HashSet<>());
//    }
//
//    public void dfs(Vertex<V,E> vertex,HashSet<Vertex<V, E>> visitedVertex){
//        System.out.println(vertex.value);
//        visitedVertex.add(vertex);
//        for(Edge<V,E> edge:vertex.outEdges){
//            if (!visitedVertex.contains(edge.to)) {
//                dfs(edge.to,visitedVertex);
//            }
//        }
//    }

    private static class Edge<V, E> {
        Vertex<V, E> from;
        Vertex<V, E> to;
        E weight;

        public Edge(Vertex<V, E> from, Vertex<V, E> to) {
            this.from = from;
            this.to = to;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Edge<V, E> edge = (Edge<V, E>) o;
            return Objects.equals(from, edge.from) && Objects.equals(to, edge.to);
        }

        @Override
        public int hashCode() {
            return from.hashCode() * 31 + to.hashCode();
        }

        @Override
        public String toString() {
            return "Edge{" +
                    "from=" + from +
                    ", to=" + to +
                    ", weight=" + weight +
                    '}';
        }

        public EdgeInfo<V,E> edgeInfo(){
            return new EdgeInfo<>(from.value, to.value, weight);
        }
    }

    private static class Vertex<V, E> {
        V value;
        Set<Edge<V, E>> outEdges = new HashSet<>();
        Set<Edge<V, E>> inEdges = new HashSet<>();

        public Vertex(V value) {
            this.value = value;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Vertex<V, E> vertex = (Vertex<V, E>) o;
            return Objects.equals(value, vertex.value);
        }

        @Override
        public int hashCode() {
            return value.hashCode();
        }

        @Override
        public String toString() {
            return "Vertex{" +
                    "value=" + value +
                    '}';
        }
    }
}
